10771. Варварские племена

На потерянной земле существуют два племени: Гареды и Кека. Они каждый год исполняют следующий ритуал: по кругу становятся n мужчин из племени Гаред (занумерованных 1, 2, ..., n) и m мужчин из племени Кека (они имеют номера n + 1, n + 2, …, n + m). Затем гуру этих племен начинает считать 1, 2, ..., k начиная с номера 1. Каждого k - ого приносят в жертву. После принесения в жертву очередных двух жителей на место второго ставят мужчину из племени, которое выбирается по правилу: если принесены в жертву двое из одинаковых племен, то выбирается мужчина из племени Гаред, если из разных – то из Кека. Процесс двух последовательных жертвоприношений и введения нового человека в круг составляют один раунд. После выполнения каждого раунда количество людей в кругу уменьшается на 1. Ритуал заканчивается, когда после очередного завершенного раунда в кругу останется один человек. Необходимо определить его племя.

Вход. Каждый тест в одной строке содержит три числа n, m, k (1 £ n + m £ 2000, 1 £ k £ 1000). Случай n = m = k = 0 обозначает конец тестов и не обрабатывается.

Выход. Для каждого теста вывести имя племени выжившего: Keka или Gared.

Пример входа

3 3 2

4 2 2

0 1 7

0 0 0

Пример выхода

Keka

Gared

Keka

РЕШЕНИЕ

математика + логика

Анализ алгоритма

После каждого раунда количество людей в кругу уменьшается на 1. Посмотрим, как будет изменяться количество людей из племен в кругу после каждого раунда.

типы раундов	превая жертва	вторая жертва	введенный	изменение Гаред	изменение Кека
1	Gared	Gared	Gared	-1	0
2	Gared	Keka	Keka	-1	0
3	Keka	Gared	Keka	-1	0
4	Keka	Keka	Gared	+1	-2

После каждого раунда количество мужчин из племени Кека изменяется либо на 0, либо на 2. То есть их четность не меняется. В конце ритуала остается один человек. Следовательно, если последним останется представитель Кека, то изначально количество мужчин из Кека было нечетным. С другой стороны в конце останется представитель Гаред, если только число людей из Кека в начале было четным.

Пример

Рассмотрим входные данные для первого теста. Изначально в кругу стоят GGGKKK (G – Гаред, K – Кека). Последовательность раундом жертвоприношений приведена в таблице (человек, с которого начинается отсчет, подчеркнут):

состояние круга	первая жертва	вторая жертва	новый введенный
GGGKKK	GGGKKK	GGGKKK	GGKKK
GGKKK	GGKKK	GGKKK	GKKK
GKKK	GKKK	GKKK	KKK
KKK	KKK	KKK	KG
KG	KG	KG	K

Реализация алгоритма

Ответ задачи зависит от четности количества людей в круге, представимых от племени Кека. То есть достаточно проверить на четность значение m и вывести результат.

while(scanf("%d %d %d",&n,&m,&k),n+m+k)

{

if (m % 2) printf("Keka\n");

else printf("Gared\n");

}